# -*- coding: utf-8 -*-

def FibonacciSearch(arr, key):
    n = len(arr)
    i = 1
    F = [1,1,]
    while F[i] <= n:
        F.append(F[i-1]+F[i])
        i += 1
    print('生成的斐波那契数', F)
    left = 0
    right = n - 1
    f = F[i]
    print('生成的最右边的斐波那契数%d' % (f))
    i = 0
    while i < f-n:
        arr.append(arr[right])
        i += 1
    print(arr)
    k = len(F)
    t = 0
    while left <= right:
        t += 1
        if k < 2:
            mid = left
        else:
            mid = left + F[k-1]-1
        print("left = %s, mid = %s, right = %s" % (left, mid, right))
        if key < arr[mid]:
            right = mid - 1
            k -= 1
        elif key > arr[mid]:
            right = mid - 1
            k -= 1
        elif key > arr[mid]:
            left = mid + 1
            k -= 2
        else:
            print("查找次数：%s" % t)
            if mid <= right:
                return mid
            else:
                return right
    print("查找次数：%s" % t)
    return False
    
key = 70
s1 = [0,3,5,7,10,30,50,70,80,100]
r = FibonacciSearch(s1, key)
if r == False:
    print('数%d在列表里没有找到！')
else:
    print('查找数%d在列表里的下标为%d' %(key, r))
